package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;
import cn.pugle.oj.catalog.Greedy;

/**
 * DP解
 * <p>
 * https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts
 *
 * @author tzp
 * @since 2020/9/17
 */
public class LC53_2 implements DynamicProblem, Greedy {
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];

        for (int i = 1; i < n; i++) {
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}
